#ifndef CIRCULARLIST_H_
#define CIRCULARLIST_H_

#include <iostream>
#include <sstream>
#include <string>
#include "myExceptions.h"

using namespace std;

template <class T>
struct chainNode 
{
   // data members
   T _element;
   chainNode<T> *_next;

   // methods
   chainNode() {}
   chainNode(const T& element)
      { _element = element; }
   chainNode(const T& element, chainNode<T>* next)
      { _element = element;
        _next = next; }
};

template <class T>
class circularChain {
	public:
	    // constructor
		circularChain();
		~circularChain();
		
		// ADT methods
		int size()      const { return _listSize; }
		int index(const T &element) const;
		void insert(int index, const T& element);
		void erase(int index);
		void out_put(ostream &os) const;
		void push_back(const T& element);
		void pop_back();
		
		bool remove(const T &element);
		void clear();
		// iterator to strat and end of list
		class iterator;
		iterator begin() { return iterator(_headerNode->_next); }
		iterator end() { return iterator(_headerNode); }
		// iterator for chain 
		class iterator
		{
			public:
			    typedef forward_iterator_tag iterator_category;
				typedef T value_type;
				typedef ptrdiff_t difference_type;
				typedef T* pointer;
				typedef T& reference;
				
				// constructor 
				iterator(chainNode<T>* node = NULL)
				        { _node = node; }
				T& operator*()  const { return _node->_element; }
				T* operator->() const { return &_node->_element; }
				
				// increment
				iterator& operator++()      // preincrement
				        { _node = _node->_next; }
				iterator operator++(int)
				        { iterator old = *this;
						  _node = _node->_next;
						  return old;}
				
				// equality testing
				bool operator!= (const iterator right) const
				        { return _node != right._node; }
				bool operator== (const iterator right) const
				        { return _node == right._node; }
			
			protected:
			    chainNode<T>* _node;
		};
	protected:
        void check_index(int index) const;
        chainNode<T>* _headerNode;
        int _listSize;		
};

template<class T>
circularChain<T>::circularChain()
{
	// constructor
	_headerNode = new chainNode<T>();
	_headerNode->_next = _headerNode;
	_listSize = 0;
}

template<class T>
circularChain<T>::~circularChain()
{
	clear();
	delete _headerNode;
	_listSize = 0;
}

template<class T>
void circularChain<T>::
check_index(int index) const
{
	if (index < 0 || index >= _listSize) {
		ostringstream s;
		s << "index = " << index << " size = "
          << _listSize;
        
		throw illegalIndex(s.str());
	}
}

template<class T>
int circularChain<T>::
index(const T& element) const
{
	
	_headerNode->_element = element;
	chainNode<T>* currentNode = _headerNode->_next;
	int index = 0;
	
	while(currentNode->_element != element) {
		currentNode = currentNode->_next;
		index ++;
	}
	
	if (currentNode == _headerNode)
		return -1;
	else 
		return index;
}

template<class T>
void circularChain<T>::
insert(int index, const T& element)
{
	if (index < 0 || index > _listSize) {
		ostringstream s;
		s << "index = " << index << " size = " << _listSize;
		throw illegalIndex(s.str());
	}
	
	chainNode<T>* p = _headerNode;
	for (int i = 0; i < index; i++)
		p = p->_next;
	
	p->_next = new chainNode<T>(element, p->_next);
		
	_listSize++;
}


template <class T>
void circularChain<T>::
erase(int index)
{
   	check_index(index);
	
	if (_headerNode->_next == _headerNode)
		return;
	
	chainNode<T>* p = _headerNode;
	chainNode<T>* deleteNode;
	
	for(int i = 0; i < index; i++)
		p = p->_next;
	
	deleteNode = p->_next;
	p->_next = deleteNode->_next;
	
	_listSize --;
	delete deleteNode;
}


template<class T>
void circularChain<T>::
push_back(const T &element)
{
	int index = _listSize;
	insert(index, element);
}

template<class T>
inline void circularChain<T>:: 
pop_back()
{
	int index = _listSize - 1;
	erase(index);
}

template<class T>
inline bool circularChain<T>::
remove(const T &element)
{
	bool ok = false;
	chainNode<T> *current = _headerNode->_next;
	
	_headerNode->_element = element;
	int index = 0;
	while (index < _listSize && current->_element != element) {
		current = current->_next;
		index ++;
	}
	
	if (index == _listSize)
		return (ok = false);
	else {
		erase(index);
		return (ok = true);
	}
}

template<class T>
inline void circularChain<T>::
clear()
{	
    if(_headerNode->_next == _headerNode)
		return;
	
	chainNode<T>* deleteNode = _headerNode->_next;
	chainNode<T>* nextNode;
	
	while (deleteNode != _headerNode) {
		nextNode = deleteNode->_next;
		delete deleteNode;
		deleteNode = nextNode;
	}
	_headerNode->_next = _headerNode;
	_listSize = 0;
}

template<class T>
inline void circularChain<T>::out_put(ostream& os) const
{// Put the list into the stream out.
   for (chainNode<T>* currentNode = _headerNode->_next;
                      currentNode != _headerNode;
                      currentNode = currentNode->_next)
      os << currentNode->_element << "  ";
}

// overload <<
template <class T>
ostream& operator<<(ostream& os, const circularChain<T> &x)
   {x.out_put(os); return os;}

#endif